package com.fanshuai.algorithms.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Range {
    /**
     * 给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。
     * [1,2],[2,3],[3,4],[1,3] 返回3
     * [10,16],[2,8],[1,6],[7,12] 返回2
     *
     * 此问题满足贪心性质：将区间按end字段升序排列，取首个元素，然后将不相交的end最小的区间放入集合
     */
    public static int intervalSchedule(int[][] intvs) {
        if (null == intvs || intvs.length == 0) {
            return 0;
        }

        //按区间end升序排序
        Arrays.sort(intvs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        //首个元素放入集合，标记集合最大end
        int end = intvs[0][1];
        int count = 1;

        for (int i = 1; i < intvs.length; i++) {
            if (intvs[i][0] >= end) { //区间不相交，元素放入集合，更新end
                count++;
                end = intvs[i][1];
            }
        }

        return count;
    }

    /**
     * 区间合并问题
     * 给定一个区间的集合，请合并所有的区间
     * 输入[1,3],[2,6],[8,10],[15,18], 输出[1,6],[8,10],[15,18]
     * 输入[1,4],[4,5], 输出[1,5]
     *
     * 此问题满足贪心性质：将区间集合按start升序排列，从首元素开始不断合并，更新当前合并的区间
     * @param intvs
     * @return
     */
    public static int[][] mergeIntervals(int[][] intvs) {
        if (null == intvs || intvs.length == 0) {
            return intvs;
        }

        //将区间列表按start排序
        Arrays.sort(intvs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> merge = new ArrayList<>();
        int curStart = intvs[0][0], curEnd = intvs[0][1];

        for (int i = 1; i < intvs.length; i++) {
            if (intvs[i][0] <= curEnd) { //区间相交，合并区间
                curEnd = intvs[i][1];
            } else { //区间不相交，将合并区间放入集合，同时更新当前区间
                merge.add(new int[] {curStart, curEnd});

                curStart = intvs[i][0];
                curEnd = intvs[i][1];
            }
        }
        merge.add(new int[] {curStart, curEnd});

        return merge.toArray(new int[merge.size()][]);
    }

    /**
     * 区间交集问题
     *
     * 给定2个由一些闭区间组成的列表，每个列表的区间互不相交，且升序排列。
     * 求2个区间列表的交集
     * 输入：A=[0,2],[5,10],[13,23],[24,25] B=[1,5],[8,12],[15,24],[25,26]
     * 输出：[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]
     *
     * 设两个指针i和j，i指向A，j指向B。
     * i和j不相交：A[i].start > B[j].end || B[j].start > a[i].end
     * A[i].start > B[j].end：j右移
     * B[j].start > a[i].end：i右移
     *
     * i和j相交：A[i].start <= B[j].end || B[j].start <= A[i].end
     * 取交集：[max(A[i].start, B[i].start), min(A[i].end, B[i].end)]
     * A[i].start <= B[j].end：j右移
     * B[j].start <= A[i].end：i右移
     * @param v1
     * @param v2
     * @return
     */
    public static int[][] intervalsIntersect(int[][] v1, int[][] v2) {
        List<int[]> intersects = new ArrayList<>();

        int i = 0, j = 0;
        while (i < v1.length && j < v2.length) {
            int a1 = v1[i][0], a2 = v1[i][1];
            int b1 = v2[j][0], b2 = v2[j][1];

            boolean b = a1 >= b1 && a1 <= b2 || b1 >= a1 && b1 <= a2;
            if (b) { //相交
                int start = Math.max(a1, b1);
                int end = Math.min(a2, b2);
                intersects.add(new int[] {start, end});

                if (a2 >= b2) {
                    j++;
                } else if (b2 >= a2) {
                    i++;
                }
            } else { //不相交
                if (a1 > b2) {
                    j++;
                } else if (a2 < b1) {
                    i++;
                }
            }
        }

        return intersects.toArray(new int[intersects.size()][]);
    }

    public static void main(String[] args) {
        int[][] a1 = {{1,2}, {2,3}, {3,4}, {1,3}};
        int[][] a2 = {{10,16}, {2,8}, {1,6}, {7,12}};

        System.out.println(intervalSchedule(a1));
        System.out.println(intervalSchedule(a2));

        int[][] a3 = {{1,3}, {2,6}, {8,10}, {15,18}};
        int[][] a4 = {{1, 4}, {4, 5}};

        int[][] merge1 = mergeIntervals(a3);
        print(merge1);

        merge1 = mergeIntervals(a4);
        print(merge1);

        int[][] a = {{0, 2}, {5, 10}, {13, 23}, {24, 25}, {31, 32}};
        int[][] b = {{1, 5}, {8, 12}, {15, 24}, {25, 26}, {41, 42}};

        int[][] intersects = intervalsIntersect(a, b);
        print(intersects);
    }

    private static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.print("\t");
        }
        System.out.println();
    }
}
